//https://leetcode.cn/problems/maximum-width-of-binary-tree/

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        unsigned int ret = 0;
        vector<pair<TreeNode*, unsigned int>> t;
        if (root == nullptr) return 0;
        t.push_back({ root,1 });

        while (t.size())
        {
            auto [x1, y1] = t[0];
            auto [x2, y2] = t.back();
            ret = max(ret, y2 - y1 + 1);

            vector<pair<TreeNode*, unsigned int>> q;
            for (auto [x, y] : t)
            {
                if (x->left) q.push_back({ x->left,2 * y });
                if (x->right) q.push_back({ x->right,2 * y + 1 });
            }
            t = q;
        }

        return ret;

    }
};